// m

// 给定一个非空字符串s和一个包含非空单词的列表wordDict，要求，判断s是否能被空格拆分为一个或者多个在字典中出现的单词

// 拆分时可以重复使用字典中的单词
// 可以假设字典中没有重复的单词

// 解题思路：动态规划
// s能否拆分为单词表的单词，可以分解为：
// 1. 前i个字符构成的字符串，能否分解为单词
// 2. 剩余字符串，能否分解为单词
// 定义状态dp[i]表示：长度为i的字符串能否拆分为单词，如果true可以拆分，如果为false则表示不能拆分
// 转移方程可以表示为：如果dp[j]可以拆分为单词，并且字符串s[j:i]出现在字典中，则dp[i] = true

function wordBreak(s, wordDict) {
    let size = s.length
    let dp = new Array(size + 1).fill(false)
    dp[0] = true
    for (let i = 0; i < size + 1; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true
            }            
        }        
    }
    return dp[size]
}
let s = "leetcode", wordDict = ["leet", "code"]
console.log(wordBreak(s, wordDict))